package com.tys.algorithm.beginner;

//测试链接：https://leetcode.com/problems/validate-binary-search-tree/submissions/
public class Code29_IsBinarySearchTree {
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    public static class Info {
        public boolean isBST;
        public int max;
        public int min;

        public Info(boolean is, int ma, int mi) {
            isBST = is;
            max = ma;
            min = mi;
        }
    }

    public boolean isValidBST(TreeNode root) {
        return process(root).isBST;
    }

    public static Info process(TreeNode x) {
        //为Null则直接返回Null,交给调用者判断
        if (x == null) {
            return null;
        }

        //递归调用左树和右树
        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);

        //找到左树和右树的最大值最小值，作为整棵树的最大值最小值
        int max = x.val;
        int min = x.val;
        if (leftInfo != null) {
            max = Math.max(leftInfo.max, max);
            min = Math.min(leftInfo.min, min);
        }
        if (rightInfo != null) {
            max = Math.max(rightInfo.max, max);
            min = Math.min(rightInfo.min, min);
        }

        boolean isBST = true;
        if (leftInfo != null && !leftInfo.isBST) {
            isBST = false;
        }
        if (rightInfo != null && !rightInfo.isBST) {
            isBST = false;
        }

        boolean leftMaxLessX = leftInfo == null ? true : (leftInfo.max < x.val);
        boolean rightMinMoreX = rightInfo == null ? true : (rightInfo.min > x.val);
        if (!leftMaxLessX || !rightMinMoreX) {
            isBST = false;
        }

        return new Info(isBST, max, min);

    }


}
